#![allow(dead_code)]
use crate::stools::{random_array, random_num};
use std::cmp::Ordering;

fn choice_sort(arr: &[i32]) -> Vec<i32> {
    let mut v: Vec<i32> = arr.into();

    for sort_idx in 0..arr.len() - 1 {
        let mut min_idx = sort_idx;
        for choice_idx in sort_idx + 1..arr.len() {
            if v[min_idx] > v[choice_idx] {
                min_idx = choice_idx;
            }
        }
        v.swap(min_idx, sort_idx);
    }

    v
}

fn bubble_sort(arr: &[i32]) -> Vec<i32> {
    let mut v: Vec<i32> = arr.into();

    for bubble_idx in (1..arr.len()).rev() {
        for idx in 1..=bubble_idx {
            if v[idx - 1] > v[idx] {
                v.swap(idx, idx - 1);
            }
        }
    }

    v
}

fn insert_sort(arr: &[i32]) -> Vec<i32> {
    let mut v: Vec<i32> = arr.into();

    for sorted_idx in 1..arr.len() {
        for i in (1..=sorted_idx).rev() {
            if v[i] < v[i - 1] {
                v.swap(i, i - 1);
            }
        }
    }

    v
}

fn binary_search(arr: &[i32]) -> i32 {
    if arr.len() == 1 {
        return arr[0];
    }

    let mid = arr.len() / 2;
    let lm = binary_search(&arr[0..mid]);
    let rm = binary_search(&arr[mid..]);

    std::cmp::max(lm, rm)
}

fn arr_merge(lv: Vec<i32>, rv: Vec<i32>) -> Vec<i32> {
    let sz = lv.len() + rv.len();
    let mut v: Vec<i32> = Vec::with_capacity(sz);
    let mut li = 0usize;
    let mut ri = 0usize;

    while li < lv.len() && ri < rv.len() {
        if lv[li] < rv[ri] {
            v.push(lv[li]);
            li += 1;
        } else {
            v.push(rv[ri]);
            ri += 1;
        }
    }
    v.extend(&lv[li..]);
    v.extend(&rv[ri..]);
    v
}

fn merge_sort(arr: &[i32]) -> Vec<i32> {
    if arr.len() == 1 {
        return arr.into();
    }

    let mid = arr.len() / 2;
    let lv = merge_sort(&arr[0..mid]);
    let rv = merge_sort(&arr[mid..]);
    arr_merge(lv, rv)
}

fn small_merge(lv: Vec<i32>, rv: Vec<i32>) -> (i32, Vec<i32>) {
    let sz = lv.len() + rv.len();
    let mut v: Vec<i32> = Vec::with_capacity(sz);
    let mut li = 0usize;
    let mut ri = 0usize;
    let mut ls = 0i32;

    while li < lv.len() && ri < rv.len() {
        if lv[li] < rv[ri] {
            v.push(lv[li]);
            ls += lv[li] * (rv.len() - ri) as i32;
            li += 1;
        } else {
            v.push(rv[ri]);
            ri += 1;
        }
    }

    v.extend(&lv[li..]);
    v.extend(&rv[ri..]);
    (ls, v)
}

fn small_sum(arr: &[i32]) -> (i32, Vec<i32>) {
    if arr.len() == 1 {
        return (0, arr.into());
    }

    let mid = arr.len() / 2;
    let (ls, lv) = small_sum(&arr[0..mid]);
    let (rs, rv) = small_sum(&arr[mid..]);
    let (s, v) = small_merge(lv, rv);

    (ls + rs + s, v)
}

fn split2part(arr: &[i32], num: i32) -> (usize, Vec<i32>) {
    let mut v: Vec<i32> = arr.into();

    let mut i: usize = 0;
    let mut nle: usize = 0;

    while i < arr.len() {
        if arr[i] <= num {
            v.swap(i, nle);
            nle += 1;
        }
        i += 1;
    }

    (nle, v)
}

fn split3part(arr: &[i32], num: i32) -> (usize, Vec<i32>) {
    let mut v: Vec<i32> = arr.into();

    let mut i: usize = 0;
    let mut nlt: usize = 0;
    let mut gt: usize = arr.len();

    while i < gt {
        match v[i].cmp(&num) {
            Ordering::Less => {
                v.swap(i, nlt);
                nlt += 1;
                i += 1;
            }
            Ordering::Greater => {
                gt -= 1;
                v.swap(i, gt);
            }
            _ => i += 1,
        }
    }

    (gt, v)
}

fn quick_sort1(arr: &[i32]) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr.into();
    }
    let privot = arr.len() - 1;

    let n = arr[privot];
    let (nidx, mut v) = split2part(&arr[..privot], n);
    v.push(n);
    v.swap(privot, nidx);
    let lv = quick_sort1(&v[0..nidx]);
    let rv = quick_sort1(&v[nidx + 1..]);

    [lv, rv].join(&n)
}

fn quick_sort2(arr: &[i32]) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr.into();
    }
    let privot = arr.len() - 1;

    let n = arr[privot];
    let (nidx, mut v) = split3part(&arr[..privot], n);
    v.push(n);
    v.swap(privot, nidx);
    let lv = quick_sort2(&v[0..nidx]);
    let rv = quick_sort2(&v[nidx + 1..]);

    [lv, rv].join(&n)
}

fn quick_sort3(arr: &[i32]) -> Vec<i32> {
    let mut v: Vec<i32> = arr.into();
    if arr.len() <= 1 {
        return v;
    }

    let lidx = arr.len() - 1;
    let privot = random_num(0..arr.len() as i32) as usize;
    let n = arr[privot];
    v.swap(privot, lidx);

    let (nidx, mut v) = split3part(&v[..lidx], n);
    v.push(n);
    v.swap(lidx, nidx);
    let lv = quick_sort2(&v[0..nidx]);
    let rv = quick_sort2(&v[nidx + 1..]);

    [lv, rv].join(&n)
}

#[derive(Debug)]
struct Heap {
    heap: Vec<i32>,
}

impl Heap {
    fn new() -> Self {
        Self { heap: Vec::new() }
    }

    fn insert(&mut self, num: i32) {
        self.heap.push(num);
        let mut nidx = self.heap.len() - 1;
        while nidx > 0 {
            let parent = (nidx - 1) / 2;
            if self.heap[parent] < self.heap[nidx] {
                self.heap.swap(parent, nidx);
            }
            nidx = parent;
        }
    }

    fn pop(&mut self) -> Option<i32> {
        if self.heap.len() <= 1 {
            return self.heap.pop();
        }

        let root = self.heap.swap_remove(0);
        let last = self.heap.len() - 1;

        let mut parent: usize = 0;
        let mut lchd: usize = 2 * parent + 1;

        while lchd <= last {
            let rchd: usize = lchd + 1;
            let max_idx = if (rchd <= last) && self.heap[rchd] >= self.heap[lchd] {
                rchd
            } else {
                lchd
            };

            if self.heap[parent] >= self.heap[max_idx] {
                break;
            }

            self.heap.swap(parent, max_idx);
            parent = max_idx;
            lchd = 2 * parent + 1;
        }

        Some(root)
    }

    fn sort(&mut self, arr: &[i32]) -> Vec<i32> {
        for num in arr {
            self.insert(*num);
        }
        let mut v: Vec<i32> = vec![];
        while let Some(num) = self.pop() {
            v.push(num);
        }

        v.into_iter().rev().collect()
    }
}

pub fn sort_main() {
    let arr = random_array(10);
    let sorted = choice_sort(&arr);
    println!("arr: {:?}", arr);
    println!("choice sort: {:?}", sorted);
    assert_eq!(choice_sort(&arr), bubble_sort(&arr));
    assert_eq!(choice_sort(&arr), insert_sort(&arr));
    assert_eq!(choice_sort(&arr), merge_sort(&arr));
    assert_eq!(choice_sort(&arr), quick_sort1(&arr));
    assert_eq!(choice_sort(&arr), quick_sort2(&arr));
    assert_eq!(choice_sort(&arr), quick_sort3(&arr));
    assert_eq!(*arr.iter().max().unwrap(), binary_search(&arr));

    let (s, v) = small_sum(&arr);
    println!("small sum: {}, v: {:?}", s, v);

    let num = random_num(0..90);
    println!("num: {}, split 2 part: {:?}", num, split2part(&arr, num));
    println!("num: {}, split 3 part: {:?}", num, split3part(&arr, num));

    let mut heap = Heap::new();
    assert_eq!(choice_sort(&arr), heap.sort(&arr));
}
